翻訳と辞書
Words near each other
・ Complete androgen insensitivity syndrome
・ Complete Arcane
・ Complete Auto Transit, Inc. v. Brady
・ Complete Best
・ Complete Best (Celine Dion album)
・ Complete Best (Sweetbox album)
・ Complete bipartite graph
・ Complete blood count
・ Complete Boolean algebra
・ Complete category
・ Complete Champion
・ Complete Charlie Parker on Dial
・ Complete circumferential peripheral and deep margin assessment
・ Complete Clapton
・ Complete Collection of Russian Chronicles
Complete coloring
・ Complete Communion
・ Complete contract
・ Complete Control
・ Complete Control Recording Sessions (Scream EP)
・ Complete Control Recording Sessions (The Bouncing Souls EP)
・ Complete Control Sessions
・ Complete Convenient
・ Complete Demos
・ Complete Discocrappy
・ Complete Discography
・ Complete Discography (disambiguation)
・ Complete Discovery Source
・ Complete Divine
・ Complete economic integration


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Complete coloring : ウィキペディア英語版
Complete coloring

In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes. The achromatic number ψ(G) of a graph G is the maximum number of colors possible in any complete coloring of G.
==Complexity theory==
Finding ψ(G) is an optimization problem. The decision problem for complete coloring can be phrased as:
:INSTANCE: a graph G=(V,E) and positive integer k
:QUESTION: does there exist a partition of V into k or more disjoint sets V_1,V_2,\ldots,V_k such that each V_i is an independent set for G and such that for each pair of distinct sets V_i,V_j,V_i \cup V_j is not an independent set.
Determining the achromatic number is NP-hard; determining if it is greater than a given number is NP-complete, as shown by Yannakakis and Gavril in 1978 by transformation from the minimum maximal matching problem.〔 A1.1: GT5, pg.191.〕
Note that any coloring of a graph with the minimum number of colors must be a complete coloring, so minimizing the number of colors in a complete coloring is just a restatement of the standard graph coloring problem.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Complete coloring」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.